#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool judgeSquareSum(int c) {
        int big = sqrt(INT_MAX);
        vector<int> vv(big + 1);
        unordered_set<int> hash;
        for (int i = 1; i <= big; ++i)
        {
            vv[i] = pow(i, 2);
            hash.insert(pow(i, 2));
        }

        int tmp = c / 2 + 1;
        for (auto& e : vv)
        {
            if (e >= tmp)
                break;

            if (hash.count(c - e) || e + e == c)
                return true;
        }

        return false;
    }
};